package leetcode.f1t100;

import java.util.ArrayList;
import java.util.List;

/**
 * 给一个唯一数组, 返回数组数字的所有排列组合
 * https://leetcode.com/problems/permutations/
 *
 * @Author lichongxiao
 * @Date 2022/10/21 15:33
 */
public class Q46_Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ansList = new ArrayList<>();
        List<Integer> ansInit = new ArrayList<>();
        ansInit.add(nums[0]);
        ansList.add(ansInit);
        for (int i = 1; i < nums.length; i++) {
            for (int j = ansList.size() -1; j >= 0 ; j--) {
                for (int k = 0; k < ansList.get(j).size(); k++) {
                    ArrayList<Integer> ans = new ArrayList<>(ansList.get(j));
                    ans.add(k,nums[i]);
                    ansList.add(ans);
                }
                ansList.get(j).add(nums[i]);
            }
        }
        return ansList;
    }

    public static void main(String[] args) {
        Q46_Permutations bean = new Q46_Permutations();
        List<List<Integer>> ansList = bean.permute(new int[]{1, 2, 3,4});
        for(List<Integer> ans : ansList){
            for(Integer num : ans){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
}
